package swardToOffer.method_2_sort_or_find.sort;

import java.util.Arrays;

/**
 * @Author ChanZany https://zhuanlan.zhihu.com/p/124356219
 * @Date 2021/5/20 10:41
 * @Version 1.0
 * 插入排序
 * 插入排序的工作方式像许多人排序一手扑克牌。
 * 它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
 * 插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
 * 复杂度O(n^2)
 * <p>
 * 冒泡排序
 * 冒泡排序的思想，是让最大的数浮动到数组最后的位置，其次大的数浮动到数组倒数第二个位置……
 * 当然，你也可以从大到小排序，也可以从后向前冒泡。其特征操作是相邻元素的比较和交换。
 * 复杂度O(n^2)
 * <p>
 * 归并排序
 * 归并排序是用分治思想，分治模式在每一层递归上有三个步骤：
 * 分解（Divide）：将n个元素分成个含n/2个元素的子序列。
 * 解决（Conquer）：用合并排序法对两个子序列递归的排序。
 * 合并（Combine）：合并两个已排序的子序列已得到排序结果。
 * 复杂度O(nlogn)
 * <p>
 * 快速排序
 * 快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
 * 该方法的基本思想是：
 * 1．先从数列中取出一个数作为基准数。
 * 2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
 * 3．再对左右区间重复第二步，直到各区间只有一个数。
 */
public class SortUtils {
    public int[] insertSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int tmp = nums[i];//保存每次需要插入的那个数
            int j;
            for (j = i; j > 0 && nums[j - 1] > tmp; j--) {
                nums[j] = nums[j - 1];//把大于需要插入的数往后移动。最后不大于temp的单位格就空出来给j
            }
            nums[j] = tmp;//将需要插入的数放入这个位置
        }
        return nums;
    }

    public int[] bubbleSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j < nums.length - i - 1; j++) {
                if (nums[j] < nums[i]) {
                    int tmp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = tmp;
                }
            }
        }
        return nums;
    }

    public void mergeSort(int[] arr) {
        int[] tmp = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1, tmp);
    }

    public void mergeSort(int[] arr, int low, int high, int[] tmp) {
        if (low >= high) return;
        int middle = (high - low) / 2 + low;
        //分
        mergeSort(arr, low, middle, tmp);
        mergeSort(arr, middle + 1, high, tmp);
        //治
        merge(arr, low, middle, high, tmp);
    }

    private void merge(int[] arr, int low, int middle, int high, int[] tmp) {
        int i = low;//左序列指针
        int j = middle + 1;//右序列指针
        int k = 0;//临时数组指针
        while (i <= middle && j <= high) {
            tmp[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
        }
        while (i <= middle) tmp[k++] = arr[i++];
        while (j <= high) tmp[k++] = arr[j++];
        //将temp中的元素全部拷贝到原数组中
        k = 0;
        while (low <= high) {
            arr[low++] = tmp[k++];
        }
    }

    public int[] mergeSort1(int[] arr) {
        int len = arr.length;
        int[] result = new int[len];
        int block, start;
        // 直接分割原数组为多个两个元素为一组的块，通过计算得到每个块的起始位置和结束位置
        for (block = 1; block < len * 2; block *= 2) {
            for (start = 0; start < len; start += 2 * block) {
                int low = start;
                int mid = Math.min((start + block), len);
                int high = Math.min((start + 2 * block), len);
                //两个块的起始下标及结束下标
                int start1 = low;
                int start2 = mid;
                //开始对两个block进行归并排序
                while (start1 < mid && start2 < high) {
                    result[low++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
                }
                while (start1 < mid) {
                    result[low++] = arr[start1++];
                }
                while (start2 < high) {
                    result[low++] = arr[start2++];
                }
            }
            int[] temp = arr;
            arr = result;
            result = temp;
        }
        result = arr;
        return result;
    }

    public void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    public void quickSort(int[] arr, int left, int right) {
        if (left > right) return;
        int i = left, j = right, x = arr[left];
        while (i < j) {
            //从右往左找第一个小于基数x的数arr[j]
            while (j > i && arr[j] >= x) {
                j--;
            }
            if (i < j) arr[i++] = arr[j];
            //从左往右找第一个大于基数x的数arr[i]
            while (i < j && arr[i] < x) {
                i++;
            }
            if (i < j) arr[j--] = arr[i];
        }
        //此时i与j相遇，i or j将原数组划分为两部分，左边的全比arr[i]小，右边的全比arr[i]大
        arr[i] = x;
        quickSort(arr, left, i - 1);
        quickSort(arr, i + 1, right);
    }

    public static void main(String[] args) {
        SortUtils sortUtils = new SortUtils();
        int[] input = {3, 2, 1, 4, 5};
//        System.out.println(Arrays.toString(sortUtils.insertSort(input)));
//        System.out.println(Arrays.toString(sortUtils.bubbleSort(input)));
//        sortUtils.mergeSort(input);
//        int[] res = sortUtils.mergeSort1(input);
//        System.out.println(Arrays.toString(res));
        sortUtils.quickSort(input);
        System.out.println(Arrays.toString(input));
    }

}
